package com.zyk.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangsan
 * @date 2021/4/4 22:11
 */
public class J39 {


    /** https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/ */
    // 暴力解
    public static int majorityElement(int[] nums) {
        HashMap<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if(entry.getValue() > nums.length/2) {
                return entry.getKey();
            }
        }
        return -1;
    }

    // 摩尔投票法
    public static int majorityElement2(int[] arr) {
        if(arr == null || arr.length == 0) {
            return -1;
        }
        int candidate = arr[0], count = 1;
        for (int i = 1; i < arr.length; i++) {
            if(count == 0) {
                candidate = arr[i];
                count++;
                continue;
            }
            if(candidate == arr[i]) {
                count++;
            }else {
                count--;
            }
        }
        // 找到了可能出现半数以上的数, 在遍历计数一下看是否正确
        count = 0;
        for (int i : arr) {
            if(i == candidate) {
                count++;
            }
        }
        return count > arr.length/2 ? candidate : -1;
    }

    // for test
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        System.out.println(
                majorityElement(nums)
        );
    }
}
